package Binary_tree;

public class Code11_PosArrayToBST {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static Node posArrayToBST(int[] posArr) {
        if (posArr == null){
            return null;
        }
        return posToBST(posArr, 0, posArr.length - 1);
    }
    // 递归
    public static Node posToBST(int[] posArr, int start, int end){
        if (start > end){
            return null;
        }
        Node head = new Node(posArr[end]);
        if (start == end){
            return head;
        }
        int root = posArr[end];
        // 找到分界点(二分)
        int left = start;
        int right = end - 1;
        int m = -1;
        while (left <= right){
            int mid = left + ((right -left) >> 1);
            if (posArr[mid] < root){ // 在右半部分找，直到找到最后一个小于根节点的节点
                left = mid + 1;
                m = mid;
            } else { // 左半部分找
                right = mid - 1;
            }
        }
        // 建左树
        head.left = posToBST(posArr, start, m);
        // 建右树
        head.right = posToBST(posArr, m + 1, end - 1);
        return head;
    }

    public static void main(String[] args) {
        int[] posArr = {1, 3, 2, 6, 8, 7, 5};
        Node head = posArrayToBST(posArr);
        System.out.println(head.value);
        System.out.println(head.left.value);
        System.out.println(head.right.value);
        System.out.println(head.left.left.value);
        System.out.println(head.left.right.value);
        System.out.println(head.right.left.value);
        System.out.println(head.right.right.value);
    }
}
